package commons;

import java.util.*;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    
    public TreeNode(int x) {
        val = x;
    }
    
    /**
     * [1,3,2,5,3,null,9]
     *
     */
    public static TreeNode make(Integer[] values) {
        TreeNode res = new TreeNode(values[0]);
        List<TreeNode> nodes = new ArrayList<>();
        nodes.add(res);
        for (int i = 1; i < values.length; i++) {
            if (values[i] == null)
                continue;
            TreeNode node = new TreeNode(values[i]);
            nodes.add(node);
            TreeNode parent = nodes.get((i - 1) >> 1);
            if ((i & 1) == 1) {
                parent.left = node;
            } else {
                parent.right = node;
            }
        }
        return res;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(this);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                if (node == null) {
                    sb.append("null").append(" - ");
                    continue;
                }
                sb.append(node.val).append(" - ");
                q.offer(node.left == null ? null : node.left);
                q.offer(node.right == null ? null : node.right);
            }
            sb.delete(sb.lastIndexOf("-") - 1, sb.length());
            sb.append("\n");
        }
        int lastLineStart = sb.lastIndexOf("\n");
        sb = new StringBuilder(sb.substring(0, lastLineStart));
        lastLineStart = sb.lastIndexOf("\n");
        int maxLen = sb.length() - lastLineStart;
        while (sb.lastIndexOf("\n", lastLineStart - 1) > 0) {
            int previousCarriage = sb.lastIndexOf("\n", lastLineStart - 1);
            int len = sb.substring(previousCarriage + 1, lastLineStart).length();
            for (int i = 0; i < (maxLen - len) / 2; i++) {
                sb.insert(previousCarriage + 1, " ");
            }
            lastLineStart = previousCarriage;
        }
        for (int i = 0; i < maxLen / 2; i++) {
            sb.insert(0, " ");
        }
        
        return sb.toString();
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        
        TreeNode node = (TreeNode) o;
        
        if (val != node.val) return false;
        if (!Objects.equals(left, node.left)) return false;
        return Objects.equals(right, node.right);
    }
    
    @Override
    public int hashCode() {
        int result = val;
        result = 31 * result + (left != null ? left.hashCode() : 0);
        result = 31 * result + (right != null ? right.hashCode() : 0);
        return result;
    }
}
